package LeetCode75;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 1679. K 和数对的最大数目
 * 给你一个整数数组 nums 和一个整数 k 。
 *
 * 每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。
 *
 * 返回你可以对数组执行的最大操作数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3,4], k = 5
 * 输出：2
 * 解释：开始时 nums = [1,2,3,4]：
 * - 移出 1 和 4 ，之后 nums = [2,3]
 * - 移出 2 和 3 ，之后 nums = []
 * 不再有和为 5 的数对，因此最多执行 2 次操作。
 * 示例 2：
 *
 * 输入：nums = [3,1,3,4,3], k = 6
 * 输出：1
 * 解释：开始时 nums = [3,1,3,4,3]：
 * - 移出前两个 3 ，之后nums = [1,4,3]
 * 不再有和为 6 的数对，因此最多执行 1 次操作。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * 1 <= nums[i] <= 109
 * 1 <= k <= 109
 */
public class T1679_K和数对的最大数目 {
    //使用map统计每个数字出现的次数
    public int maxOperations(int[] nums, int k) {

        //Integer可以作为key  它的hashcode方法 直接返回整数   和equals方法 重写过 直接判断数值是否相等
        Map<Integer, Integer> numCountMap = new HashMap<>();
        int result = 0;
        Arrays.sort(nums);
        for (int num : nums) {
            if (numCountMap.containsKey(num)) {
                numCountMap.put(num,numCountMap.get(num)+1);
            }else {
                numCountMap.put(num,1);
            }
        }

        int i = 0;
        //num[i]<=k 是为了减少遍历次数 第一个数已经大于K了 就不存在第二个数了 (为啥不能是负数 因为数组已经排过序了 负数在前面已经遍历过了 剩余的数都是大于firstNUm的)
        while (i<nums.length&&nums[i]<=k){
            int firstNum = nums[i];
            if (findTwoNum(numCountMap,firstNum,k)){
                result++;
            }
            i++;
        }

        return result;


    }

    //使用双指针 排序后 左右指针
    //将两个指针指向的数求和；
    //若和大于目标，则说明太大了，需要右指针左移（可以使和变小）；
    //若和小于目标，则说明太小了，需要左指针右移（可以使和变大）；
    //若和等于目标，则两个指针都往中间移动，结果+1。
    public int maxOperations2(int[] nums, int k) {
        int left = 0;
        int right = nums.length-1;
        int result = 0;
        Arrays.sort(nums);
        while (left<right){
            if (nums[left]+nums[right]>k){
                right--;
            }else if (nums[left]+nums[right]<k){
                left++;
            }else {
                right--;
                left++;
                result++;
            }
        }
        return result;

    }

    //在map 中找到数对 并成功删除
    public boolean findTwoNum(Map<Integer,Integer> map,int firstNum,int k){

        int secondNum = k-firstNum;
        if (!map.containsKey(firstNum)){
            return false;
        }

        if (!map.containsKey(secondNum)) {
            return false;
        }
        //删除第一数
        if (map.get(firstNum)>=1){
            map.put(firstNum,map.get(firstNum)-1);
        }else {
            return false;
        }
        //删除第二个数
        if (map.get(secondNum)>=1){
            map.put(secondNum,map.get(secondNum)-1);
        }else {
            //删除第二个数失败 应该将第一个数加回来 但是这里 并不影响结果
            return false;
        }

        return true;

    }
}
